function match (P, S) { // KMP 算法
  let next = buildNext(P); // 构造 next 表
  let m = S.length, i = 0; // 文本串指针
  let n = P.length, j = 0; //模式串指针
  // 自左向右逐个比对字符
  while (j < n && i < m) {
    // 若匹配，或 P 已移除最左侧
    if (0 > j || S[i] == P[j]) {
      // 则转到下一字符
      i++
      j++
    } else {
      // 模式串右移（注意：文本串不用回退）
      j = next[j];
    } 
  }
  if (j < m) return -1
  return i - j;
}

function buildNext(P) { // 构造模式串 P 的 next 表
  let m = P.length, j = 0; // “主”串指针
  let N = []; // next 表
  let t = N[0] = -1; // 模式串指针
  while (j < m - 1) {
    // 匹配
    if ( 0 > t || P[j] == P[t]) {
      j++; t++;
      N[j] = t; // 此句可改进为 N[j] = (P[j] != P[t] ? t : N[t]);
    }else {
      // 失配
      t = N[t];
    }
  }
  return N;
}
